Graph Neural Networks ,A Review of Methods and Applications

发表于

Introduction

  原文地址

  图是一种建模一组节点和它们之间关系的数据结构。近来，使用机器学习分析图的研究受到了越来越多的关注，因为图具有强大的表达能力，比如，图可以被应用在大量种类的系统中，包括社会科学（社交网络），自然科学（物理系统，蛋白质交互网络），知识图和其他研究领域。作为一种独特的非欧几里得的数据结构，对于机器学习来说，图分析集中在节点分类，链路预测和聚类。图神经网络（GNNs）是基于深度学习的方法，其在图域上操作。因为其令人信服的表现和高可解释性，GNN已经成为了广泛应用的图分析方法。
  Motivations：

  • GNNs的第一个动机根植于CNNs。

    • CNNs的关键是：局部连结，参数共享和使用多层网络
    • 图是最典型的局部连结结构
    • 和传统的频谱图理论相比，参数共享可以减少计算代价
    • 多层网络结构是处理层次模式的关键，其可以捕获不同尺寸的特征

  • 第二个动机来源于图嵌入（graph embedding）

    • 基于CNNs和 图嵌入，GNNs被提出来聚合来自于图结构的信息。因此，GNNs可以建包含元素和它们之间关系的输入或是输出。
    • 此外，GNNs还可以使用 RNN kernel 同时建模图的扩散过程

  为什么GNNs值得研究：

  1. 像CNN和RNN这样的标准神经网络无法正确处理图形输入，因为它们按特定顺序堆叠节点的特征。而GNNs在每个节点上分别传播，忽略节点的输入顺序。
  2. 图中的边表示两个节点之间的依赖信息。 在标准神经网络中，依赖信息仅被视为节点的特征。 但是，GNN可以通过图结构进行传播，而不是将其用作特征的一部分。
  3. 推理是高级人工智能的一个非常重要的研究课题，人脑中的推理过程几乎都是基于从日常经验中提取的图形。

  此文包含：

  • GNN的原始模型和其变体，和一些通用框架
  • GNNs的应用：结构化场景，非结构化场景和其他场景
  • 未来研究的四个开放问题

Model

Graph Neural Network

  这部分介绍原始的图卷积网络，及其在表示能力和训练效率方面的限制。

  在一个图中，每一个节点自然地由它的特征和相关节点所定义。GNN的目标是学习到状态嵌入（state embedding）$h_v \in \mathbb{R}^s$ ，其包含每个节点的邻居的信息。状态嵌入$h_v$是节点 $v$ 的 $s$ 维向量，可被用来产生输出 $o_v$，比如节点标签。令 $f$ 是参数函数，称为局部转变函数，其在所有节点之中共享，并根据输入的邻居更新节点状态。令 $g$ 为局部输出函数，其描述了输出是如何产生的。然后，$h_v$ 和 $o_v$ 定义如下：

equal 1 2

  令 $H,O,X$ 和 $X_N$ 是分别通过堆叠所有状态，所有输出，所有特征和所有节点特征构造的向量。于是我们得到一种紧凑形式：

equal 3 4

  根据巴拿马不动点理论，GNN使用下面的经典迭代方案来计算状态：

equal 5

  当我有拥有了GNN框架之后，接下来的问题就是如何学习 $f$ 和 $g$ 的参数。对于监督学习，具有目标信息 $t_v$，损失可被写作如下形式：

equal 6

其中 $p$ 是有监督节点的数目。学习算法基于梯度下降策略，由如下步骤组成。

  • 状态 $h_v^t$ 由 Eq.1 迭代的更新，直到时间 T。它们到达 Eq.3 的不动点解决方案：$H(T) \approx H$
  • 根据 loss 计算权重 $W$ 的梯度
  • 根据上一步计算出来的梯度更新权重$W$

  Limitations：

  1. 对于不动点，迭代地更新节点的隐藏状态不高效。如果松弛不动点假设，可以设计多层网络的GNN来获得节点及其邻居更稳定的表示
  2. GNN在迭代中使用相同的参数，然而大多数流行的神经网络在不同层使用不同的参数，作为一个层次特征提取器。此外，节点隐藏状态的更新是顺序过程，不能从RNN kernel受益。
  3. 在边上的信息特征不能被原始GNN 高效建模。
  4. 如果我们聚焦于节点表示而不是图表示的话，使用不动点假设是不合适的，因为在不动点假设中，表示的分布会更在值上更平滑，具有少量信息来区分节点。

Variants of Graph Neural Networks

  这一部分作者介绍了几种GNN的变体。该部分的第一部分聚焦于在不同图类型上操作的变体，这些变体扩展了原始模型的表示能力；第二部分列出了在传播步骤上的修改（卷积，门机制，注意力机制和跳跃连结）的变体；第三部分描述了使用先进训练方法的变体。

  图类型：

Graphy Types

  传播步骤：

Propagation steps

  训练方法

training methods

Table 2

通用框架

  一些通用框架被提出来旨在将不同的方法整合到单一框架中。message passing neural network（MPNN），统一了各种GNN和GCN 方案；non-local neural network（NLNN），统一了一些自注意风格的方法；graph network（GN）统一了 MPNN，NLNN和其他变体。

   Message Passing Neural Networks

  MPNN框架抽象了几种最流行的图结构数据模型之间的共性，例如图卷积中频谱方法和非光谱方法，门控图神经网络，交互网络，分子图卷积，深张量神经网络等等。

  该模型包含了两个阶段：信息传递阶段和读出阶段。消息传递阶段（传播步骤）运行 $T$ 个时间步，根据消息函数 $M_t$ 和顶点更新函数 $U_t$ 所定义。使用消息 $m_v^t$ ，隐藏状态 $h_v^t$ 的更新函数如下：

equal 34

读出阶段使用读出函数 $R$ 计算整个图的特征向量：

equal 35

消息传递函数，顶点更新函数和读出函数可以具有不同的设置，因此 MPNN 可以泛化到一些不同的模型。

  Non-local Neural Networks

  非局部运算是计算机视觉中经典非局部均值运算的推广。非局部运算将某一位置的响应计算为所有位置特征的加权和。这组位置可以在空间、时间或时空中。 因此，NLNN 可以被视为不同“自注意”方式的统一。

  遵循非局部平均运算，通用非局部运算定义如下：

equal 37

$i$ 是输出位置的索引，$j$ 是所有可能位置的索引。$f(h_i,h_j)$可以看作是表示两点之间关系的一个标量。$g(h_j)$ 表示输入 $h_j$ 的转换。$\frac{1}{C(h)}$用来为归一化系数。

  Graph Networks

  图定义：在 GN 中，一个图被定义为一个三元组 $G = (u,H,E)$。$u$ 是全局属性，$H = \{h_i\}_{i=1:N^v}$ 是顶点集，其中 $h_i$ 是顶点的属性。$E=\{(e_k,r_k,s_k)\}_{k=1:N^e}$ 是边集合，$e_k$ 是边属性，$r_k$ 和 $s_k$ 分别是接受点和发送点的索引。

  GN block：

GN block

  计算步骤：

Computation steps

  注意这里次序并不是严格要求的。

Applications

  作者将应用分为三个场景：（1）结构化场景，其中数据具有显示的关系结构，如物理系统，分子结构和知识图谱（2）非结构化场景，其中关系结构并不是显示的，如图片，文本等。（3）其他应用场景如生成模型和和组合优化问题。

结构化场景

  1. 物理。对现实世界的物理系统进行建模是理解人类智能的最基本方面之一。通过将对象表示为节点，将关系表示为边，我们可以以简化但有效的方式执行关于对象，关系和物理的基于GNN的推理。
  2. 化学和生物学
    • 分子手印
    • 蛋白质界面预测
  3. 知识图谱

非结构化场景

  1. 图片
    • 图片分类
    • 视觉推理
    • 语义分割
  2. 文本
    • 文本分类
    • 序列标注
    • 神经机器翻译
    • 关系抽取
    • 事件抽取

其他场景

  1. 生成模型
    • 建模社交交互
    • 发现新的化学结构
    • 构建知识图谱
  2. 组合优化问题
    • TSP
    • 二次分配问题，如衡量两个图的相似性

Open problems

  1. 浅结构
    • 堆叠多层GCN 网络层会导致过平滑问题（over-smooth），也就是所有顶点会收敛到相同值
  2. 动态图
    • 如何处理具有动态结构的图
    • 当点或边出现或消失时，GNN不能适应性改变
  3. 非结构场景
    • 没有从原始数据中生成图的最佳方法
  4. 可扩展性
    • 在大数据环境下，GNN的许多核心步骤都具有很大的计算开销。